home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / kwiksort.c < prev    next >
C/C++ Source or Header  |  1992-10-16  |  5KB  |  237 lines
  1. /*
  2.    An animated quick sort program.  Based on the recursive Quicksort
  3.     algorithm in "Algorithms + Data Structures = Programs" by Niklaus Wirth,
  4.     Prentice-Hall, Inc., 1976,  ISBN 0-13-022418-9.  See chapter 2, section
  5.     2.2.6.
  6.  
  7.     Note that there are better ways of actually implementing the Quicksort
  8.     algorithm.
  9.  
  10.     If you have a version of the compiler prior to TC++, you'll need to
  11.     replace the calls to _setcursortype() with something else (or nothing).
  12.  
  13.     Released to the public domain by the author.
  14.     Gary M. Blaine   CIS 70007,4659
  15. */
  16.  
  17. #include <stdlib.h>
  18. #include <conio.h>
  19. #include <time.h>
  20. #include <bios.h>
  21. #include <dos.h>
  22.  
  23. /* function prototypes */
  24. void Quicksort(char* letters, int left, int right);
  25. void inc(int* n);
  26. void dec(int* n);
  27. void display(char* letters, int i, int j);
  28. void init_arrows(int i, int j);
  29. void swap(char* letters, int i, int j);
  30.  
  31. #define SIZE 40
  32.  
  33. int main(void)
  34. {
  35.    char letters[SIZE];
  36.    int  i;
  37.  
  38.    randomize();
  39.     _setcursortype(_NOCURSOR);        
  40.    clrscr();
  41.  
  42.    for(i = 0; i < SIZE; i++)                 /* initialize the array */
  43.       letters[i] = random(26) + 'A';
  44.  
  45.    display(letters, 0, SIZE-1);              /* display the array */
  46.  
  47.    Quicksort(letters, 0, SIZE-1);            /* sort the array */
  48.  
  49.    gotoxy(1, 3);
  50.     _setcursortype(_NORMALCURSOR);
  51.    return 0;
  52. }
  53.  
  54. /* sort an array of letters */
  55. void Quicksort(char* letters, int left, int right)
  56. {
  57.    int  i, j;
  58.    char x;
  59.  
  60.    /* display initial left and right pointers */
  61.    init_arrows(left, right);
  62.  
  63.    i = left;
  64.    j = right;
  65.     x = letters[(left+right) / 2];
  66.  
  67.    /* do the partition */
  68.    do
  69.       {
  70.       while(letters[i] < x)  inc(&i);
  71.       while(letters[j] > x)  dec(&j);
  72.       if(i <= j)
  73.          {
  74.          swap(letters, i, j);
  75.          inc(&i);
  76.          dec(&j);
  77.          }
  78.       }
  79.    while(i <= j);
  80.  
  81.    /* sort left partition */
  82.    if(left < j)
  83.       Quicksort(letters, left, j);
  84.  
  85.    /* sort right partition */
  86.    if(i < right)
  87.       Quicksort(letters, i, right);
  88.  
  89.    /* clear away the little arrow pointers */
  90.    gotoxy(1, 1);
  91.    clreol();
  92. }
  93.  
  94. /* increment a variable and update arrow position */
  95. void inc(int* n)
  96. {
  97.    int row = 1;
  98.    int col = *n * 2 + 1;
  99.  
  100.    gotoxy(col, row);       /* get rid of little arrow */
  101.    putch(' ');
  102.  
  103.    (*n)++;                 /* increment the variable in calling function */
  104.  
  105.    col = *n * 2 + 1;       /* display the new arrow location */
  106.    gotoxy(col, row);
  107.    putch(0x19);            /* a down pointing arrow */
  108.  
  109.    delay(100);
  110. }
  111.  
  112. /* decrement a variable and update arrow position */
  113. void dec(int* n)
  114. {
  115.    int row = 1;
  116.    int col = *n * 2 + 1;
  117.  
  118.    gotoxy(col, row);       /* get rid of little arrow */
  119.    putch(' ');
  120.  
  121.    (*n)--;                 /* decrement the variable in calling function */
  122.  
  123.    col = *n * 2 + 1;       /* display the new arrow location */
  124.    gotoxy(col, row);
  125.    putch(0x19);            /* a down pointing arrow */
  126.  
  127.    delay(100);
  128. }
  129.  
  130. /* display the array */
  131. void display(char* letters, int i, int j)
  132. {
  133.    int n;
  134.    int row = 1 + 1;
  135.  
  136.    for(n=i; n<=j; n++)
  137.       {
  138.       gotoxy(n*2+1, row);
  139.       putch(letters[n]);
  140.       }
  141. }
  142.  
  143. /* swap array elements */
  144. void swap(char* letters, int i, int j)
  145. {
  146.    int row  = 2;
  147.    int rowi = 3;
  148.    int rowj = 4;
  149.  
  150.    int mi, mj;
  151.  
  152.    char ci = letters[i];                  /* remember the characters at i, j */
  153.    char cj = letters[j];
  154.  
  155.    char tmp   = letters[i];            /* swap array elements */
  156.    letters[i] = letters[j];
  157.    letters[j] = tmp;
  158.  
  159.    /* move ith character down */
  160.    for(mi = row; mi < rowi; mi++)   
  161.       {
  162.       gotoxy(i*2+1, mi);
  163.       putch(' ');
  164.       gotoxy(i*2+1, mi+1);
  165.       putch(ci);
  166.       delay(100);
  167.       }
  168.  
  169.    /* move jth character down */
  170.    for(mj = row; mj < rowj; mj++)   
  171.       {
  172.       gotoxy(j*2+1, mj);
  173.       putch(' ');
  174.       gotoxy(j*2+1, mj+1);
  175.       putch(cj);
  176.       delay(100);
  177.       }
  178.  
  179.    /* move characters horizontally */
  180.    for(mi=i*2+1, mj=j*2+1; mi<j*2+1; mi++, mj--)
  181.       {
  182.       gotoxy(mi, rowi);
  183.       putch(' ');
  184.       gotoxy(mj, rowj);
  185.       putch(' ');
  186.  
  187.       gotoxy(mi+1, rowi);
  188.       putch(ci);
  189.       gotoxy(mj-1, rowj);
  190.       putch(cj);
  191.       delay(20);
  192.       }
  193.  
  194.    /* move ith character back up into jth position */
  195.    for(mi = rowi; mi > row; mi--)
  196.       {
  197.       gotoxy(j*2+1, mi);
  198.       putch(' ');
  199.       gotoxy(j*2+1, mi-1);
  200.       putch(ci);
  201.       delay(100);
  202.       }
  203.  
  204.    /* move jth character back up into ith position */
  205.    for(mj = rowj; mj > row; mj--)
  206.       {
  207.       gotoxy(i*2+1, mj);
  208.       putch(' ');
  209.       gotoxy(i*2+1, mj-1);
  210.       putch(cj);
  211.       delay(100);
  212.       }
  213.  
  214.    /* let the user quit by hitting any key */
  215.    if( bioskey(1) )
  216.       {
  217.       bioskey(0);
  218.       gotoxy(1, 3);
  219.       cputs("User terminated");
  220.         _setcursortype(_NORMALCURSOR);
  221.       exit(1);
  222.       }
  223. }
  224.  
  225. /* display the little arrow pointers */
  226. void init_arrows(int i, int j)
  227. {
  228.    gotoxy(1, 1);        /* get rid of any existing arrows */
  229.    clreol();
  230.  
  231.    gotoxy(i*2+1, 1);
  232.    putch(0x19);         /* a down pointing arrow */
  233.  
  234.    gotoxy(j*2+1, 1);
  235.    putch(0x19);         /* a down pointing arrow */
  236. }
  237.